/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-03-03
 * Time:10:49
 */
public class TestDemo {
    /**
     * 258. 各位相加
     * 给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果
     * 输入: num = 38
     * 输出: 2
     * 解释: 各位相加的过程为：
     * 38 --> 3 + 8 --> 11
     * 11 --> 1 + 1 --> 2
     * 由于 2 是一位数，所以返回 2。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/add-digits
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static void main1(String[] args) {
        int num = 40;
        while (num > 9) {
            num = addDigits(num);
        }
        System.out.println(num);
    }

    //递归版本
    public static int addDigits(int num) {
        if (num / 10 == 0) {
            return num;
        }
        return num % 10 + addDigits(num / 10);
    }

    public static void main2(String[] args) {
        System.out.println(addDigits1(0));
    }

    //非递归版本
    public static int addDigits1(int num) {
        if (num <= 9) {
            return num;
        }
        int ans = 0;
        while (num > 9) {
            ans = 0;
            while (num / 10 != 0) {
                ans += num % 10;
                num /= 10;
            }
            ans += num;
            num = ans;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        System.out.println(subArrayRanges1(nums));
    }
    //2104. 子数组范围和
    /**给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
     返回 nums 中 所有 子数组范围的 和 。
     子数组是数组中一个连续 非空 的元素序列

     来源：力扣（LeetCode）
     链接：https://leetcode-cn.com/problems/sum-of-subarray-ranges
     著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
    //暴力求解 跟滑窗类似;
    public static long subArrayRanges(int[] nums) {
        long n = nums.length;
        int sum = 0;
        for (int i = 1; i < n; i++) {
            int min = nums[i];
            int max = nums[i];
            for (int j = i - 1; j >= 0; j--) {
                int cur = nums[j];
                max = Math.max(max,cur);
                min = Math.min(min,cur);
                sum+=(max-min);
            }
        }
        return sum;
    }
    //区间 DP-三叶
    //f[l][r][0]存的是lr区间的最小值 f[l][r][1]存的是lr区间的最大值
        public static long subArrayRanges1(int[] nums) {
            int n = nums.length;
            int[][][] f = new int[n][n][2];
            for (int i = 0; i < n; i++) f[i][i][0] = f[i][i][1] = nums[i];
            for (int len = 2; len <= n; len++) {
                for (int l = 0; l + len - 1 < n; l++) {
                    int r = l + len - 1;
                    f[l][r][0] = Math.min(nums[r], f[l][r - 1][0]);
                    f[l][r][1] = Math.max(nums[r], f[l][r - 1][1]);
                }
            }
            long ans = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    ans += f[i][j][1] - f[i][j][0];
                }
            }
            return ans;
        }
}